package club.xiaojiawei.greedy;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/26/22 1:15 PM
 * @question 53. 最大子数组和
 * @description 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 */
public class MaxSubArray53 {

    public static void main(String[] args) {
        MaxSubArray53 test = new MaxSubArray53();
        int result = test.maxSubArray(new int[]{-2, -3, -1});
        System.out.println("最大和为："+result);
    }

    /**
     * dp
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        if (length == 1){
            return nums[0];
        }
        int amount = nums[0];
        int max = amount;
        for (int i = 1; i < length; i++) {
            if (amount >= 0){
                if (nums[i] < 0 && -nums[i] >= amount){
                    amount = 0;
                }else {
                    max = Math.max(max, amount += nums[i]);
                }
            }else if (nums[i] > amount){
                max = Math.max(max, amount = nums[i]);
            }else {
                amount += nums[i];
            }
        }
        return max;
    }

    /**
     * 官方-dp
     * 时间复杂度为 O(n)
     * 空间复杂度 O(1)
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    /**
     * 官方-分治（线段树）
     * 时间复杂度为 O(n)
     * 空间复杂度 O(logn)
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    public static class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }
}
